/**
 * //给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。
 * //
 * // 编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。
 * //
 * // 示例 1:
 * //
 * // 输入:
 * //beginWord = "hit",
 * //endWord = "cog",
 * //wordList = ["hot","dot","dog","lot","log","cog"]
 * //
 * //输出:
 * //["hit","hot","dot","lot","log","cog"]
 * //
 * //
 * // 示例 2:
 * //
 * // 输入:
 * //beginWord = "hit"
 * //endWord = "cog"
 * //wordList = ["hot","dot","dog","lot","log"]
 * //
 * //输出: []
 * //
 * //解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
 * // Related Topics 广度优先搜索 哈希表 字符串 回溯 👍 59 👎 0
 */

package com.xixi.basicAlgroithms.BreadthWidthFirstSearch;

import java.util.*;

public class ID_interview_17_22_WordTransformerLcci {
    public static void main(String[] args) {
        Solution solution = new ID_interview_17_22_WordTransformerLcci().new Solution();


        System.out.println(solution.findLadders("a", "c", Arrays.asList(new String[]{"a", "v", "c"})));
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        List<String> pathList = new ArrayList<>();
        HashSet<String> wordSet = new HashSet<>();
        //回溯
        boolean finished = false;
        List<HashMap<Character, HashSet<String>>> adjacentList = new ArrayList<>();

        //BFS
        boolean[] visited = null;
        HashMap<String, String> prevPathMap = null;


        public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {


            //回溯，先建立一个每一步的可选列表，也就是每个字符的邻接表
            for (int i = 0; i < beginWord.length(); i++) {//处理第i位
                adjacentList.add(new HashMap<>());
                for (int j = 0; j < wordList.size(); j++) { //处理每个词的第i位置
                    String nowWordStr = wordList.get(j);
                    char[] nowWord = nowWordStr.toCharArray();
                    HashMap<Character, HashSet<String>> nowStepMap = adjacentList.get(i);
                    HashSet<String> charWordSet = nowStepMap.get(nowWord[i]);
                    if (charWordSet == null) {
                        charWordSet = new HashSet<>();
                    }
                    charWordSet.add(nowWordStr);
                    wordSet.add(nowWordStr);
                    nowStepMap.put(nowWord[i], charWordSet); //字母：单词Set
                }
            }
            //BFS
            //防止成环
            visited = new boolean[wordList.size()];
            prevPathMap = new HashMap<>(wordList.size());

            if (!wordSet.contains(endWord)) return Collections.emptyList(); //不存在

            return BFS(beginWord, endWord, wordList);

            //然后一个字母一个字母转变,每一步都在hashSet中判断一下是否存在，不存在就尝试下一个字母

//            backTracking(endWord, beginWord);
//            return pathList;

        }

        public List<String> BFS(String startWord, String endWord, List<String> wordList) {

            boolean founded = false;

            Queue<String> nextStepQueue = new ArrayDeque<>();
            nextStepQueue.offer(startWord);


            while (!founded && !nextStepQueue.isEmpty()) {
                String nowWord = nextStepQueue.poll();

                for (int i = 0; i < wordList.size(); ++i) {
                    if (!visited[i] && ableToJump(nowWord, wordList.get(i))) { //如果能跳
                        nextStepQueue.offer(wordList.get(i));
                        prevPathMap.put(wordList.get(i), nowWord); //记录前一跳单词
                        if (wordList.get(i).equals(endWord)) { //找到了
                            founded = true;
                            break;
                        }
                        visited[i] = true; //被遍历过
                    }
                }
            }

            if (founded) {
                foundPath(prevPathMap, endWord, startWord);
                return pathList;
            } else {
                return Collections.emptyList();
            }

        }


        //递归找到最开始的单词
        public void foundPath(HashMap<String, String> prevPathMap, String preWord, String beginWord) {

            if (beginWord.equals(prevPathMap.get(preWord))) {
                pathList.add(beginWord);
                pathList.add(preWord);
                return;
            }
            String nextPreWord = prevPathMap.get(preWord);
            foundPath(prevPathMap, nextPreWord, beginWord);
            pathList.add(preWord);

        }


        //能否跳到下一个单词,如果只有一位不同，就可以跳,小于或超过一位都不行
        public boolean ableToJump(String startWord, String nextWord) {
            int differenceNum = 0;
            char[] startChar = startWord.toCharArray();
            char[] nextChar = nextWord.toCharArray();

            for (int i = 0; i < startWord.length(); ++i) {
                if (startChar[i] != nextChar[i]) {
                    ++differenceNum;
                }
            }

            return differenceNum == 1;

        }

        public void backTracking(String endWord, String midWord) {
            if (finished) {
                return;
            }
            pathList.add(midWord); //先放到路径里
            if (endWord.equals(midWord)) {
                finished = true;
                return;
            }

            char[] midChar = midWord.toCharArray();

            for (int i = 0; i < adjacentList.size(); i++) { //每一个词位开始转换

                HashMap<Character, HashSet<String>> nowCharsMap = adjacentList.get(i);

                for (Map.Entry<Character, HashSet<String>> entry : nowCharsMap.entrySet()) { //遍历每个可能性
                    char nowChar = entry.getKey();
                    if (midChar[i] != nowChar) { //待跳转的词
                        char tmp = midChar[i]; //临时保存曾经的字符
                        //修改
                        midChar[i] = nowChar;
                        String newMid = new String(midChar);
                        if (wordSet.contains(newMid)) { //如果这一步包含在字典中，继续递归
                            wordSet.remove(newMid);//此路不通
                            backTracking(endWord, newMid);
                            if (finished) {
                                return;
                            }

                        }
                        //恢复
                        midChar[i] = tmp;
                    }
                }


            }


            pathList.remove(pathList.size() - 1);

        }


    }
//leetcode submit region end(Prohibit modification and deletion)


}